Step 1: Standard Merge Sort

First, let's implement the standard Merge Sort. This ensures we have the correct recursive structure before we add the complexity of counting inversions.

Implementation Details

  • Base Case: If the list has 0 or 1 elements, it is already sorted.
  • Divide: Find `mid` and recursively sort `arr[:mid]` and `arr[mid:]`.
  • Compare & Merge: Iterate through both `left` and `right`.
  • Condition: To sort in ascending order, if `left[i]` is smaller or equal to `right[j]`, append `left[i]`. 
def merge_sort(arr):
    # 1. Base Case
    if len(arr) <= 1:
        return arr

    # 2. Divide
    mid = len(arr) // 2
    
    # RECURSIVE CALLS: Sort left & right
    left = ____
    right = ____

    # 3. Merge
    merged = []
    i = 0; j = 0

    while i < len(left) and j < len(right):
        
        # Check if left is smaller/equal
        if ____: 
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged
Copied!